﻿#pragma once
#include "Index.h"

class ISort
{
public:
	virtual void sort(std::vector<int>& vals) = 0;
};

class SortSolution
{
public:
	static void swap(int& a,int& b)
	{
		a = a ^ b;
		b = a ^ b;
		a = a ^ b;
	}
public:
	class BubbleSort : public ISort
	{
	public:
		void sort(std::vector<int>& vals) override
		{
			const int vals_size = vals.size();
			//往右冒泡选出最大值需要进行的轮次
			for(int i=0;i<vals_size-1;++i)
			{
				//从左到右通过不断交换选出最大值
				for(int j=0;j<vals_size-1-i;++j)
				{
					if (vals[j] > vals[j + 1])
						swap(vals[j], vals[j + 1]);
				}
			}
		}
	};
	class BubbleSortWithSwapMark : public ISort
	{
	public:
		void sort(std::vector<int>& vals) override
		{
			const int vals_size = vals.size();
			//当一轮冒泡没有发生交换时,说明此时剩余的数字已经有序
			bool swaped = true;
			
			//往右冒泡选出最大值需要进行的轮次
			for (int i = 0; i < vals_size - 1; ++i)
			{
				if (!swaped) break;

				swaped = false;
				//从左到右通过不断交换选出最大值
				for (int j = 0; j < vals_size - 1 - i; ++j)
				{
					if (vals[j] > vals[j + 1])
					{
						swap(vals[j], vals[j + 1]);
						swaped = true;
					}
				}
			}
		}
	};
	class BubbleSortWithSwapMarkAndSwapIndex : public ISort
	{
	public:
		void sort(std::vector<int>& vals) override
		{
			const int vals_size = vals.size();

			//下一个等待冒泡交换得到较大值的位置
			int wait_bubble = vals_size - 1;
			//当一轮冒泡没有发生交换时,说明此时剩余的数字已经有序
			bool swaped = true;

			//只要每轮冒泡交换有发生就一直继续
			while(swaped)
			{
				swaped = false;
				int swaped_index = -1;
				//从左到右通过不断交换选出最大值
				for (int j = 0; j < wait_bubble; ++j)
				{
					if (vals[j] > vals[j + 1])
					{
						swap(vals[j], vals[j + 1]);
						swaped = true;
						swaped_index = j;
					}
				}

				if (swaped)
					wait_bubble = swaped_index;
			}
		}
	};
};

#ifdef DEV_TEST
#include <gtest/gtest.h>
#include "TestingUtil.h"
class SortSolutionTest :public testing::Test
{
public:
	void testSort(ISort* solution)
	{
		std::vector<int> vals_to_sort = TestingUtil::randRangeInts(10000, -1000, 1000);
		std::vector<int> sorted_vals = vals_to_sort;
		std::sort(sorted_vals.begin(), sorted_vals.end());

		solution->sort(vals_to_sort);

		for (int i = 0; i < vals_to_sort.size(); ++i)
			EXPECT_EQ(vals_to_sort[i], sorted_vals[i]);
	}
};
TEST_F(SortSolutionTest,bubbleSort_basic)
{
	testSort(new SortSolution::BubbleSort());
}
TEST_F(SortSolutionTest,bubbleSort_swapMark)
{
	testSort(new SortSolution::BubbleSortWithSwapMark());
}
TEST_F(SortSolutionTest,bubbleSort_swapMark_swapIndex)
{
	testSort(new SortSolution::BubbleSortWithSwapMarkAndSwapIndex());
}
#endif